package ljl.alg.jianzhioffer.round2;

/**
 * 长得很丑的数
 * */
public class _49_nth_ugly_number {
    
    /*
    * 1 2 3 4 5 6 8 9
    *
    * 我记着是搞三个数，然后每轮求个 min 啥的
    *
    * 我想了想，要记录上一轮的 ugly
    * 找到最小的数，看看乘以几可以大于 ugly，然后它就乘那个数，ugly 变成大点的那个数
    *
    * 有点漏洞，ugly 要看是不是比最大的那个数大，如果大了才乘
    * 不然只需要找出来三个数里比 ugly 大的就行了
    *
    * 还是有漏洞，比如 2 3 5 吧，2 * 2 是比 5 小的，所以得选 2 * 2 不能选 5
    * 那就得选 a b c 和 min(a, b, c) * 2/3/5 里最小的那个了？哦？
    *
    * 1 1 2
    * 1 2 3
    * 下一个数是 4，不是 5；4 是 2 * 2，怎么找到这个数呢？我干？
    *
    * 想不出来，操他妈，看答案了
    * */
    public int nthUglyNumber_煞笔(int n) {
        int a = 1, b = 1, c = 1; // 这三个数说不好谁乘几，不能叫 n2 n3 n5
        int res = 1;
        while (n-- > 0) {
            int min = Math.min(a, Math.min(b, c));
            if (min * 2 > res) res = min * 2;
            else if (min * 3 > res) res = min * 3;
            else res = min * 5;
            System.out.println("min: " + min + ", res: " + res);
            if (min == a) a = res;
            else if (min == b) b = res;
            else c = res;
        }
        return res;
    }
    
    /**
     * dp
     * 记录三个指针，是前面三个丑数
     * 找到*2 *3 *5 最小的那个数作为新的丑
     * 指针增加
     *
     * 错了，我以为我懂了，开始写了，其实没懂
     *
     * a b c 这三个，分别负责 *2 *3 *5，永远不变！
     * 怎么想到的，我是想不到
     *
     * 三个指针，交错前进，如万马奔腾，乱的一批
     * 太草了！
     * */
    public int nthUglyNumber(int n) {
        int a = 0, b = 0, c = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            int a2 = dp[a] * 2, b3 = dp[b] * 3, c5 = dp[c] * 5;
            int min = Math.min(a2, Math.min(b3, c5));
            dp[i] = min;
            // 三个指针都不变倒是不可能
            // 不过可能两个指针都变了，因为会出现最小公倍数，也就是相等的情况
            // 具体怎么分析，我他妈就不管了
            if (min == a2) a++;
            if (min == b3) b++;
            if (min == c5) c++;
        }
        return dp[n - 1];
    }
}
